#
# Design a stack that supports push, pop, top, and retrieving the minimum 
# element in constant time.
#

# @author:timlentse(tinglenxan@gmail.com)
# @Date:2014-11-15
class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []
       # @param x, an integer
       # @return an integer
    def push(self, x):
		self.stack.append(x)
		if (self.minStack and x== self.minStack[-1][0]):
		    self.minStack[-1] = (x,self.minStack[-1][1]+1)
		elif not self.minStack or x < self.minStack[-1][0]: 
		    self.minStack.append((x,1))
		return x   

      # @return nothing
    def pop(self):
        if (self.top() == self.getMin()):
            if (self.minStack[-1][1] > 1):
                self.minStack[-1] = (self.minStack[-1][0],self.minStack[-1][1]-1)
            else:
                self.minStack.pop()
        self.stack.pop()

      # @return an integer
    def top(self):
    	return self.stack[-1]     

      # @return an integer
    def getMin(self):
    	return self.minStack[-1][0]

    